package 算法.NiuKe.JZ;

/**
 * @author: 谢君臣
 * @create: 2021-01-20 10:57
 * @founction: 在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
 * 请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
 * 输入
 * 7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
 * 返回值
 * true
 */
public class JZ1 {
    public static void main(String[] args) {
        int[][] array = {{}};
        int k = 0;
        System.out.println(Find(k, array));
    }

    public static boolean Find(int target, int[][] array) {
        if (array[0].length==0)
            return false;
        int x = 0, y = 0; // 压缩矩阵
        for (int i = 0; i < array.length; i++) {
            if (array[0][i] < target) {
                y++;
            } else if (array[0][i] > target) {
                break;
            } else {
                return true;
            }
        }
        for (int i = 0; i < array.length; i++) {
            if (array[i][0] < target) {
                x++;
            } else if (array[i][0] > target) {
                break;
            } else {
                return true;
            }
        }
        if (x>0&&y>0&&array[x - 1][y - 1] < target) {
            return false; // 举证最大值都小于目标数
        } else {
            for (int i = x-1; i >= 0; i--) {
                for (int j = y-1; j >= 0; j--) {
                    if (array[i][j]==target)
                        return true;
                }
            }
            return false;
        }
    }
}
